package __回溯算法

/*
*
https://leetcode.cn/problems/palindrome-partitioning/

131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：
输入：s = "a"
输出：[["a"]]
*/
var (
	path131 []string // 放已经回文的子串
	res131  [][]string
)

func partition(s string) [][]string {
	path131, res131 = make([]string, 0), make([][]string, 0) //初始化数组
	dfs131(s, 0)                                             //调用递归函数

	return res131
}
func dfs131(s string, curStart int) {
	//递归出口, 退出条件
	if curStart == len(s) { // 如果起始位置等于s的大小，说明已经找到了一组分割方案了
		temp := make([]string, len(path131))
		copy(temp, path131)
		res131 = append(res131, temp)
		return
	}
	//开始遍历字符串元素
	for i := curStart; i < len(s); i++ {
		str := s[curStart : i+1]
		if isPalindrome(str) { // 是回文子串
			path131 = append(path131, str)
			dfs131(s, i+1)                     // 寻找i+1为起始位置的子串
			path131 = path131[:len(path131)-1] // 回溯过程，弹出本次已经添加的子串
		}
	}
}

// 判断是否为字符串
func isPalindrome(s string) bool {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}
